//
//  Dijkstra.h
//

#pragma once

#include "Graph.h"
#include "UnvisitedNode.h"
#include <vector>
#include <queue>
#include <iostream>
#include "PreviousNode.h"

using namespace std;

class UnvisitedComparison
{
public:
    bool operator() (const UnvisitedNode* unvisited1, const UnvisitedNode* unvisited2) const {
        // Tengo que ordenar por cantidad de saltos y desempatar por k restante
        // porque tengo que marcar como visitados a los nodos llegando con el mayor k posible con que
        // se puede a esos nodos
        if(unvisited1->jumpsSoFar == unvisited2->jumpsSoFar) {
            return unvisited1->kLeft < unvisited2->kLeft;
        }
        return unvisited1->jumpsSoFar > unvisited2->jumpsSoFar;
    }
};
// priority queue de PreviousNode implementada sobre vector
// sacar e insertar elementos tiene costo logaritmico
typedef priority_queue<UnvisitedNode*,std::vector<UnvisitedNode*>, UnvisitedComparison> UnvisitedPQ;


class Dijkstra
{
    UnvisitedPQ unvisited;
    int k;
    void initializeNodes();
    void createPrevNodes();
public:
    Graph* graph;
    
    Dijkstra(Graph* graph, int k);
    
    void findPath(Node* fromNode, Node* toNode);
    
};
